/**
 * @author LKQ
 * @date 2021/12/24 16:49
 * @description 递归翻转，利用后续遍历，先反转左子树，后翻转右子树，然后返回根节点
 */
public class FormalSolution {
    public static void main(String[] args) {

    }

    /**
     * 后续遍历，先翻转左子树，后翻转右子树，然后根节点
     * @param root root
     * @return 翻转
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    /**
     * 利用中序遍历翻转
     * @param root root
     */
    public void invertTreeByInorder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 递归找到左节点
        invertTreeByInorder(root.left);
        // 保存右节点
        TreeNode right = root.right;
        // 进行交换
        root.right = root.left;
        root.left = right;
        // 交换之后，递归找到右节点，也就是交换之后的左节点
        invertTreeByInorder(root.left);
    }



    /**
     * 利用先序遍历--从顶向下交换
     * @param root root
     * @return 翻转
     */
    public TreeNode invertTree2(TreeNode root) {
        if (root == null) {
            return null;
        }
        // 保存右子树
        TreeNode rightTree = root.right;
        // 交换左右子树的位置
        root.right = invertTree(root.left);
        root.left = invertTree(rightTree);
        return root;
    }
}
